As integrated circuit (IC) devices (also referred to as semiconductor devices) advance technologically, many designers and applications are calling for physically smaller ICs. Advanced patterning techniques have been developed in order to meet the design constraints associated with these smaller devices without sacrificing IC performance. For example, multiple patterning techniques, such as double patterning and/or triple patterning of masks and/or IC layers may be used to meet design constraints in smaller devices (e.g., at the 14 nanometer (nm) node, and potentially beyond this node). This multiple patterning allows for devices and features to be formed (e.g., printed) at a closer proximity relative to one another over the course of multiple prints. In multiple patterning, one of the key steps is decomposition, where the features are separated into individual masks, such that when combined during lithography, they produce the desired features on the wafer without any defects. Typically, decomposition is performed in either a manual fashion, through the IC designer, or using an automated decomposition tool, which is capable of splitting a layout into separate masks for the multiple exposures.
However, with multiple patterning, the decomposition of a layout into e.g., two exposures by itself may not guarantee that the desired patterning and electrical behavior are produced in the completed IC. That is, it is also helpful to ensure that the density of shapes on both masks (in the double-patterning example) remains balanced and spaced appropriately, in order to ensure uniform etch behavior, and consequently uniform electrical performance. This balance may be difficult to achieve during the design process, or manual decomposition, due to IC size and design processes which include the work of several individual IC designers whom are responsible for smaller sub-areas of the IC which may inadvertently conflict. Further, it is also prohibitively time consuming to achieve density balancing using an automated decomposition tool, because of the need to solve a complex optimization problem on a large scale. Conventional approaches of designing layouts for multiple patterning processes are deficient in producing the desired result.